1. Field of the Invention
The present invention relates generally to ring type network data transmission systems, and more particularly to a method and apparatus for gracefully inserting and removing stations from a ring type network.
2. Description of Related Art
Data transmission systems enable a number of stations to communicate with each other at high speeds over long distances. The combination of a data transmission system and a number of stations coupled to the data transmission system is commonly known as a network.
A station may be any one of a number of different types of devices, including computers and printers. Such stations typically include hardware and software for coupling the station to a data transmission system, thus forming a data input link from the data transmission system and a data output link to the data transmission system. The data input link allows the station to receive data from the data transmission system, and thus from other stations in the network. The data output link allows the station to send data to the data transmission system and thus to other stations in the network.
A "ring" is a common network topology. One common ring network is the token ring network according to The Institute of Electrical and Electronics Engineers (IEEE), Local Area Network Standard 802.5. Another common ring network standard is the American National Standard Institute (ANSI) Fiber Distributed Data Interface (FDDI). One advantage of rings over other topologies is that relatively simple protocols can be used to organize the transmission of data around the ring. Another advantage of rings is that as data arrives at each station, the data is simply passed from the data input link of a station to that station's data output link. The only routing decision that a station must make during normal use is whether the data is addressed to that station, in which case the data must be copied by the station.
It is well known to house at least part of the hardware and software for interfacing a station to a data transmission system in a hub device, also known as a concentrator. Typically a concentrator may interface several stations to a network.
Referring now to FIG. 1, a concentrator 100 is shown which connects several stations to a data transmission system, such as a ring type network. The concentrator 100 is coupled to a station through one or more port interface(s) 110. The concentrator 100 has a data input link 101, and a data output link 102. Such data input links from a ring are commonly known as "RingIns". Such data output links to a ring are commonly known as "RingOuts". These data links 101, 102 couple the concentrator 100 to the ring. Each port interface 110 also includes a RingIn 111 and a RingOut 112, which facilitate connecting stations in a ring configuration through the port interlaces 110. The concentrator 100 may also have a multiplexer 103 and internal data path 104 that allows a ring to be formed within the concentrator 100, effectively connecting RingIn 111 to RingOut 142. The concentrator 100 may also include a media access controller (MAC) 140 for the ring. The MAC 140 controls and mediates access for information exchange with other stations on the ring.
It is well known that since a concentrator 100 has both RingIn 101 and RingOut 102, a concentrator 100 may be inserted into a ring as if the concentrator 100 were a station. Because of this capability, the term "tree" is used to describe stations connected to a ring through a port interface 110.
Referring now to FIG. 2, each port interface 110 comprises a RingIn 111, a RingOut 112, a tree output link (TreeOut) 113, and a tree input link (TreeIn) 114. Master port logic 117 is coupled to the TreeIn 114 and TreeOut 113. The master port logic 117 comprises encoding/decoding circuits, clock logic, line state logic (including idle generation logic), etc. Two multiplexers 210, 220 are provided to direct data within the port interface 110. One multiplexer 210 receives data from the RingIn 111 and the TreeIn 114 (through the master port logic 117), and outputs data to the TreeOut 113 (through the master port logic 117); the other multiplexer 220 receives data from the RingIn 111 and the TreeIn 114 (through the master port logic 117), and outputs data to the RingOut 112.
Typically, a station that "logs into" or enters a ring type network interrupts normal data transmission and causes a recovery process in the network. Referring now to FIG. 3, according to one method, "insertion" of a tree into a ring type network takes place as follows:
A. The multiplexer 220 within a concentrator 100 routes all data from a RingIn 111 to a RingOut 112 (STEP 300). PA1 B. The connection between the tree and a master port of a concentrator 100 is initialized (STEP 310). PA1 C. The multiplexer 210 switches the RingIn 111 to the TreeOut 113 (STEP 320). PA1 D. The multiplexer 220 switches the TreeIn 114 to the RingOut 112 (STEP 330). PA1 A. The connection between the tree and the port interface 117 of the concentrator 400 is initialized (STEP 610). This may include switching of the multiplexer 510 to provide various data patterns to be transmitted to the tree. PA1 B. Multiplexer 510 within the port interface 410 in the concentrator 400 switches LocalIn 415 to TreeOut 113 and the multiplexer 560 switches the TreeIn 114 to LocalOut 416 (STEP 620). PA1 C. A claim process with the Local MAC 450 to is forced make T.sub.-- Neg within the connecting station's MAC and Ring MAC equal (STEP 630). PA1 D. The local MAC 450 captures the token on the local ring. Capturing the token on the local ring halts data transmission to the local ring 460 (STEP 640). PA1 E. The ring MAC 440 captures the token on the network ring. Capturing this token halts data transmission on the network ring (STEP 650). PA1 F. The ring MAC 440 holds the network token long enough to allow any frames on the network to be delivered to the destination station. This prevents disruption of data transmission (STEP 660). PA1 G. The multiplexer 510 switches the RingIn 111 to the TreeOut 113 (STEP 670). PA1 H. The multiplexer 520 switches the TreeIn 114 to the RingOut 112 (STEP 680). PA1 J. The value of T.sub.-- Neg stored in the ring MAC 440 associated with the network ring is checked to ensure that the value had not changed during insertion (STEP 690). PA1 K. The multiplexer 560 switches the LocalIn 415 to the LocalOut 416 (STEP 695).
As is known, a recovery process typically follows physical connection of the tree to the concentrator 100, as described above. This recovery process takes time and, as a result, consumes network bandwidth and increases queuing delays for information awaiting transmission on the network. A distinguishing characteristic of these networks is that information received from an upstream neighbor is inspected by a particular station and, in some cases, is repeated to a downstream neighbor. Since stations of this type invariably store some information as part of this repeating process, the insertion of a station can corrupt frames that are in transit on the network.
To overcome such problems, a number of techniques, known generally as "graceful insertion," have been proposed which minimize the probability that insertion of a station will cause either a network recovery, or frame corruption, to occur. Referring to FIG. 4, in one graceful insertion system, a concentrator 400 has a second local ring 460 coupling a plurality of port interfaces 410. The port interfaces 410 are coupled to a data transmission system (network ring) and trees, as described above. A local media access controller (MAC) 450 is also coupled to the local ring 460, in known fashion. The concentrator 400 may also have a multiplexer 103 and internal data path 104 that allows a ring to be formed within the concentrator 400.
Referring now to FIG. 5, it can be seen that each port interface 410 includes three multiplexers 510, 520, 560. Two of these multiplexers 510, 520, are substantially the same as the multiplexers 210, 220, described above. The third multiplexer 560 receives data from a data link (LocalIn) 415 to the local ring 460 and a TreeIn 114 (through a master port logic 117), and outputs data on a data link (LocalOut) 416 to the local ring 460. The LocalIn 415 is also coupled to the multiplexer 510. Referring now to FIG. 6, one software controlled graceful insertion technique for inserting a tree into an FDDI ring network functions as follows (the initial state is RingIn 111 to RingOut 112, and LocalIn 415 to LocalOut 416):
I. The token is released by the ring MAC 440 on the network ring (STEP 685).
In this prior art method, the MAC event interrupts and insertion protocols are executed while the token on the network ring is captured and held by the ring MAC 440 in the concentrator 400. This consumes what would have otherwise been useful network bandwidth. To avoid destroying frames, the token must be held by the ring MAC 440 long enough to allow any frames on the network to be delivered to a destination station. In general, this is less efficient than a normal insertion operation specified in the FDDI standard, referred to above.
Many graceful insertion implementations, such as the one described above, rely on software for time critical operations that are a part of the insertion process. Prior art graceful insertion methods decrease ring bandwidth less than normal insertion only in very large networks. Yet, such prior art graceful insertion systems reduce the number of claim processes and retransmissions of frames damaged during insertion. However, there remains a probability of insertion failure (e.g., holding a token for too long or releasing the token before insertion is complete).
It is therefore an object of the present invention to provide graceful insertion while minimizing the probability of an insertion failure and minimizing bandwidth required. It is a further object of the present invention to provide upgradability of existing concentrators to include such capabilities.
These objects and others are provided in the apparatus and method of the present invention.